Digital data transmissions over wired and wireless channels sometimes may be corrupted, for instance, by noise in the link or channel, by interference from other transmissions, or by other environmental factors. Even with clear communication channels, which lend themselves to high data rates, it may not be possible to appropriately decode the data stream with the requisite error rates. In order to solve this problem, many communication systems employ error-correction techniques to aid in communication.
One technique utilized for error correction is the convolutional coding of information to be transmitted. Utilizing such a technique, an encoder will encode the information bits from an information vector into data symbols at a fixed encoding rate with an encoding algorithm which facilitates subsequent decoding of the data symbols into information bits (e.g., maximum a posteriori decoding algorithms, maximum likelihood decoding algorithms). Generally, information bits are encoded using a rate 1/R0 mother code. Since over-the-channel transmission rates may differ from the encoding rate, the encoded data needs to be modified to match the over-the-channel transmission rate. Prior art techniques for matching the rate of encoding to the over-the-channel transmission rate have used an appropriate puncturing pattern.
For example, the encoded data symbols from a rate ½ (i.e., R0=2) mother code may be divided into groups of 6 (corresponding to 3 information bits). Then a puncturing pattern of (1, 0, 1; 1, 1, 0) is applied to each group to achieve an over-the-channel rate of ¾, where a ‘1’ indicates that the encoded symbol is retained while a ‘0’ indicates that the encoded symbol is punctured (i.e., not transmitted). Although this puncturing pattern is fairly simple, puncturing patterns can often be fairly complicated for different rates (e.g., rate 0.4177). Puncturing patterns are typically generated by exhaustive searches that match each combination of data rate, the encoding rate, and over-the-channel transmission rate. As a result, introducing new data rates, encoding rates, or over-the-channel transmission rates into a communication system can be difficult.
Furthermore, prior art techniques for puncturing often complicate the implementation of incremental redundancy (IR) hybrid automatic repeat request (HARQ). With incremental redundancy, the information bits are re-transmitted where each transmission corresponding to the same information vector may use a different puncturing pattern. Because puncturing patterns may overlap, there may be a loss in performance with incremental redundancy. For example, assuming a rate ½ mother code (i.e., encoding rate=½), the first transmission uses a rate ⅘ puncturing pattern of (1, 1, 0, 1; 0, 1, 0, 1). If the second transmission uses a puncturing pattern of (0, 0, 1, [21 zeros]), then the first and the second transmission can be combined to form a rate ¾ code. However, if the second transmission uses the (1, [23 zeros]) pattern, then IR degenerates into partial Chase combining, resulting in performance loss. In addition, this example requires the information block size to be a multiple of 12 to achieve the exact code rate of ⅘ after the first transmission, and rate ¾ after the second transmission. This example illustrates the inflexibility of the puncturing pattern approach in providing the required code rate for forward error correction (FEC) and IR systems.
Although several methods exist to solve the rate matching problem for turbo codes, the same methods cannot be applied to convolutional codes. For example, the IEEE 802.16 standard contains a rate-matching procedure for turbo codes. The turbo encoder takes an information stream and produces a systematic stream and an even number of parity streams. Half of the parity streams are produced using a turbo interleaved version of the information stream. The rate-matching arranges the bits in the streams in a manner suitable for iterative turbo decoding by (a) rearranging the bits in each stream using additional (identical) block interleavers and (b) giving the information stream higher priority for transmission. However, a convolutional code may not even produce an information stream, and even if it does produce an information stream, the performance may be degraded if the information stream is prioritized. Therefore, a need exists for a method and apparatus for generating a punctured symbol vector for a given information vector for convolutional codes.